#define  _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int* GetNext(const char* dest, int len)
{
	int* next = (int*)malloc(sizeof(int)*len);
	assert(next);
	next[0] = -1;
	next[1] = 0;
    const char* sub = dest;

	int i = 2;
	int k = 0;
	while (i < len)
	{
		if (k == -1 || sub[i - 1] == sub[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}

	return next;
}

int test(const char* dest, const char* src, int len1, int len2)
{
	assert(dest && src);

	int* next = GetNext(src, len2);

	int i = 0;
	int j = 0;
	while (i < len1 && j < len2)
	{
		if(dest[i] == src[j])
		{
			if (j == -1 || dest[i] == src[j])
			{
				i++;
				j++;
			}
			else
			{
				j = next[j];
			}
		}
	}

	free(next);

	return j == len2 ? i - j : -1;
}

int main()
{


	return 0;
}